Conventional turbo decoders are created using two conventional maximum a posteriori (MAP) decoders. A conventional MAP decoder implements equations 1-4 as follows:                                                                                           log                  e                                ⁢                                  Λ                  k                                            =                                                log                  e                                ⁢                                                                            ∑                                                                        u                          k                                                =                                                  +                          1                                                                                      ⁢                                          p                      ⁡                                              (                                                  u                          ,                          y                                                )                                                                                                                        ∑                                                                        u                          k                                                =                                                  -                          1                                                                                      ⁢                                          p                      ⁡                                              (                                                  u                          ,                          y                                                )                                                                                                                                                                    =                                                                    ∑                                                                  u                        k                                            =                                              +                        1                                                                              ⁢                                                            α                      k                                              s                        ′                                                              ⁢                                          γ                      k                                                                        s                          ′                                                ,                        s                                                              ⁢                                          β                                              k                        +                        1                                            s                                                                                                            ∑                                                                  u                        k                                            =                                              -                        1                                                                              ⁢                                                            α                      k                                              s                        ′                                                              ⁢                                          γ                      k                                                                        s                          ′                                                ,                        s                                                              ⁢                                          β                                              k                        +                        1                                            s                                                                                                                              Eq        .                                   ⁢                  (          1          )                                                  α                      k            +            1                    s                =                              ∑                          s              ′                                ⁢                                    α              k                              s                ′                                      ⁢                          γ              k                                                s                  ′                                ,                s                                                                        Eq        .                                   ⁢                  (          2          )                                                  β          k                      s            ′                          =                              ∑            s                    ⁢                                    γ              k                                                s                  ′                                ,                s                                      ⁢                          β                              k                +                1                            s                                                          Eq        .                                   ⁢                  (          3          )                                                  γ                                    s              ′                        ,            s                          =                  exp          [                                    ∑              i                        ⁢                                          y                i                            ⁢                              s                i                                              ]                                    Eq        .                                   ⁢                  (          4          )                    
The variable Λk is a ratio of a probability that a kth bit is +1 to a probability that the kth bit is −1, given an encoder input signal sequence u and a received signal sequence y, and loge Λk is a log likelihood ratio (LLR). The variable αks′ is a forward state metric of state s′. The variable βk−1s is a reverse state metric of state s. The state metrics α and β are calculated recursively by the expressions shown in equations (2) and (3). The variable γks′,s is a branch metric, a quantity proportional to a probability that a transition is made from state s′ to state s. The variable yi is an ith received noisy code word having the state si.
In a conventional hardware implementation, the product αks′γks′,sβk−1s of equation 1 is more efficiently implemented by a sum. The sum is accomplished by a transformation of the variables α, β and γ by taking logarithms as shown in equations 5-7 as follows:{circumflex over (α)}=logeα  Eq. (5) 
{circumflex over (β)}=logeβ  Eq. (6)                               γ          ^                =                                            log              e                        ⁢            γ                    =                                    ∑              i                        ⁢                                          y                i                            ⁢                              s                i                                                                        Eq        .                                   ⁢                  (          7          )                    The products in the summations in equation 1 become additions as shown in equation 8 as follows:                                                                                           log                  e                                ⁢                                  Λ                  k                                            =                                                log                  e                                ⁢                                                                            ∑                                                                        u                          k                                                =                                                  +                          1                                                                                      ⁢                                                                  e                                                                              α                            ^                                                    k                                                      s                            ′                                                                                              ⁢                                              e                                                                              γ                            ^                                                    k                                                                                    s                              ′                                                        ,                            s                                                                                              ⁢                                              e                                                                              β                            ^                                                                                k                            +                            1                                                    s                                                                                                                                                ∑                                                                        u                          k                                                =                                                  -                          1                                                                                      ⁢                                                                  e                                                                              α                            ^                                                    k                                                      s                            ′                                                                                              ⁢                                              e                                                                              γ                            ^                                                    k                                                                                    s                              ′                                                        ,                            s                                                                                              ⁢                                              e                                                                              β                            ^                                                                                k                            +                            1                                                    s                                                                                                                                                                                            =                                                log                  e                                ⁢                                                                            ∑                                                                        u                          k                                                =                                                  +                          1                                                                                      ⁢                                          exp                      ⁡                                              [                                                                                                            α                              ^                                                        k                                                          s                              ′                                                                                +                                                                                    γ                              ^                                                        k                                                                                          s                                ′                                                            ,                              s                                                                                +                                                                                    β                              ^                                                                                      k                              +                              1                                                        s                                                                          ]                                                                                                                        ∑                                                                        u                          k                                                =                                                  -                          1                                                                                      ⁢                                          exp                      ⁡                                              [                                                                                                            α                              ^                                                        k                                                          s                              ′                                                                                +                                                                                    γ                              ^                                                        k                                                                                          s                                ′                                                            ,                              s                                                                                +                                                                                    β                              ^                                                                                      k                              +                              1                                                        s                                                                          ]                                                                                                                                                    Eq        .                                   ⁢                  (          8          )                    Rather than summing the products of the state metrics and branch metrics, calculation of the LLR becomes a summation of the exponentials of the sum of the state metrics and branch metrics. The summation can be computed using conversions shown in equations 9 and 10 as follows:loge(eA+eB)=max(A, B)+log(1+e−|A−B|) =max*(A, B)  Eq. (9) max*(A, B, C)=max*(max*(A, B), C)  Eq. (10) The maximum-log function (max*) can be interpreted as a maximum function max(A, B) with a correction factor loge (1+e−|A−B|). With the conversions, the MAP decoder equations can be expressed in terms of max* functions. The forward state metric equation in terms of the max* function is shown in equations 11 and 12, for illustration, as follows:                               α                      k            +            1                    s                =                              ∑                          s              ′                                ⁢                                    α              k                              s                ′                                      ⁢                          γ              k                                                s                  ′                                ,                s                                                                        Eq        .                                   ⁢                  (          11          )                                                                                                              α                  ^                                                  k                  +                  1                                s                            =                                                                    log                    e                                    ⁢                                      α                                          k                      +                      1                                        s                                                  =                                                      log                    e                                    ⁢                                                            ∑                                              s                        ′                                                              ⁢                                                                  α                        k                                                  s                          ′                                                                    ⁢                                              γ                        k                                                                              s                            ′                                                    ,                          s                                                                                                                                                                                            =                                                log                  e                                ⁢                                                      ∑                                          s                      ′                                                        ⁢                                      exp                    ⁡                                          [                                                                        α                          k                                                      s                            ′                                                                          +                                                  γ                          k                                                                                    s                              ′                                                        ,                            s                                                                                              ]                                                                                                                                              =                                                max                  *                                ⁢                                  (                                                            ∑                                              s                        ′                                                              ⁢                                          (                                                                                                    α                            ^                                                    k                                                      s                            ′                                                                          +                                                                              γ                            ^                                                    k                                                                                    s                              ′                                                        ,                            s                                                                                              )                                                        )                                                                                        E        ⁢                                   ⁢                  q          .                                           ⁢                      (            12            )                              
Referring to FIG. 1, a conventional core circuit 10 of a conventional turbo decoder architecture is shown. A received bit signal (i.e., Y) and extrinsic information signal (i.e., E) are used to calculate branch metric signals (i.e., γ) in a branch metrics circuit 12. The branch metric signals γ are summed with state metric signals (i.e., α1 and βj) in a state metrics circuit 14 to determine the state metrics for a next state metric signal (i.e., αi−1 and βj−1). The sums (i.e., intermediate signals α+γ and β+yγare also passed onto a log likelihood ratio (LLR) circuit 16. The LLR circuit 16 calculates multiple log likelihood ratios that determined the most likely data transitions. The LLR circuit 16 then presents the most likely data transitions in a data signal (i.e., U).
A bottleneck of the conventional turbo decoder core circuit 10 is the state metrics circuit 14. Because of the recursive nature of operations within the state metrics circuit 14, introduction of pipeline architecture cannot improve the overall throughput of the core circuit 10. Successive state metrics are calculated in a specific sequence.
Referring to FIG. 2, a detailed block diagram of the conventional state metrics circuit 14 is shown. The state metrics circuit 14 performs multiple operations, an addition 17, a maximum-log (MAX*) operation 18, a maximum (MAX) operation 20, and a normalization (NORM) operation 22. Values of the forward state metric signals {circumflex over (α)}k and the branch metric signals {circumflex over (γ)}k are summed 17 and the max* function applied in the maximum-log operation 18 to generate a next forward state metric signal {circumflex over (α)}k+1′. Calculation of a next reverse state metric signal (not shown) is performed in a similar manner. The maximum operation 20 is then performed on the next forward state metric signal {circumflex over (α)}k+1′ to generate a normalization signal (i.e., N).
The value of the next forward state metric signal {circumflex over (α)}k+1′ needs to be normalized because the next forward state metric signal {circumflex over (α)}k+1′ is representing numbers with a finite number of bits. All of the original forward state metric signals α are also normalized to maintain a proper relative amplitude. The next forward state metric signal {circumflex over (α)}k+1′ and the forward state metric signals α are then normalized by a value of the normalization signal N in the normalization operation 22. Since the normalization operation 22 depends on the results of the maximum-log operation 18 and the maximum operation 20, the steps executed by the circuits 18, 20, and 22 are inherently sequential. For example, a conventional core circuit 10 fabricated by a conventional 0.25 micron technology resulted in a synthesized delay of 16.3 nanoseconds.